#include <iostream>
#include <cmath>
#include <fstream>
#include <chrono>
#include <algorithm>

using namespace std;

void print_first_last_30(int nums[], int size) {
    cout << "First 30 elements: ";
    for (int i = 0; i < 30; ++i) {
        cout << nums[i] << " ";
    }
    cout << endl;

    cout << "Last 30 elements: ";
    for (int i = size - 30; i < size; ++i) {
        cout << nums[i] << " ";
    }
    cout << endl;
}

void bubble_sort(int nums[], int size) {
    bool is_sorted = true;
    bool is_reverse_sorted = true;

    for (int i = 0; i < size - 1; ++i) {
        if (nums[i] > nums[i + 1]) {
            is_sorted = false;
        }
        if (nums[i] < nums[i + 1]) {
            is_reverse_sorted = false;
        }
    }

    if (is_sorted) {
        return;
    }
    if (is_reverse_sorted) {
        reverse(nums, nums + size);
        return;
    }

    for (int i = 0; i < size - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < size - 1 - i; ++j) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

void read_to_array(const string& filename, int nums[], int size) {
    ifstream file(filename);
    for (int i = 0; i < size; ++i){
        file >> nums[i];
    }
}

int main() {
    const int SIZE = 5000;
    int nums[SIZE];

    const string filenames[] = {"m1_sorted.txt", "m2_reverse.txt", "m3_shuffle.txt"};

    for (const auto& filename : filenames) {
        read_to_array(filename, nums, SIZE);
        // print_first_last_30(nums, SIZE);
        auto start_time = chrono::high_resolution_clock::now();
        bubble_sort(nums, SIZE);
        auto end_time = chrono::high_resolution_clock::now();
        
        chrono::duration<double, milli> elapsed_time = end_time - start_time;
        cout << filename.substr(0, filename.find('.')) << " " << round(elapsed_time.count()) << " milliseconds" << endl;
        // print_first_last_30(nums, SIZE);
    }

    return 0;
}